#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;


/***
 *
 *329. 矩阵中的最长递增路径
困难
726
相关企业
给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。



示例 1：


输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4
解释：最长递增路径为 [1, 2, 6, 9]。
 https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/description/
 *
 *
 * */

//唉卧槽我这个怎么调试也不对
//vector<int> res1;
//vector<vector<int>> visited;
//int res=0;
//vector<int> temp;
//int maxRow=0;
//int maxCol=0;
//void dfs(vector<vector<int>>& matrix,int rowIndex,int colIndex )
//{
//    if (rowIndex<0||rowIndex>maxRow ||colIndex<0||colIndex>maxCol)
//    {
//        return;
//    }
//    int t=visited[rowIndex][colIndex];
//    if (t==1)
//        return;
//
//    visited[rowIndex][colIndex]=1;
//    if (temp.empty() || (matrix[rowIndex][colIndex]>temp.back()))
//    {
//        temp.push_back(matrix[rowIndex][colIndex]);
//        if (res<temp.size())
//        {
//            res=temp.size();
//            res1=temp;
//        }
//    }else
//        return;
//
//    dfs(matrix,rowIndex+1,colIndex);
//    dfs(matrix,rowIndex-1,colIndex);
//    dfs(matrix,rowIndex,colIndex+1);
//    dfs(matrix,rowIndex,colIndex-1);
//    visited[rowIndex][colIndex]=0;
//
//
//    if (!temp.empty()&&temp.back()==matrix[rowIndex][colIndex])
//       temp.pop_back();
//
//}
//
//int longestIncreasingPath(vector<vector<int>>& matrix) {
//
//    maxRow=matrix.size()-1;
//    maxCol=matrix[0].size()-1;
//    visited.resize(maxRow+1,vector<int>(maxCol+1,0));
//    for (int i = 0; i <=maxRow ; ++i) {
//
//        for (int j = 0; j <=maxCol ; ++j) {
//            temp.clear();
//            visited.clear();
//            visited.resize(maxRow+1,vector<int>(maxCol+1,0));
//            dfs(matrix,i,j);
//        }
//
//    }
//
//    return res;
//
//}
int maxCol = 0;
int maxRow = 0;

int dfs(vector<vector<int>> &matrix, vector<vector<int>> &visit, int pre, int row, int col) {
    if (col < 0 || row < 0 || col >= maxCol || row >= maxRow || matrix[row][col] <= pre)
        return 0;//返回一个小值

    //记忆递归 如果找到值了 就直接返回

    if (visit[row][col] > 0)
        return visit[row][col];

    int l = dfs(matrix, visit, matrix[row][col], row - 1, col);

    int r = dfs(matrix, visit, matrix[row][col], row + 1, col);

    int up = dfs(matrix, visit, matrix[row][col], row, col + 1);

    int down = dfs(matrix, visit, matrix[row][col], row, col - 1);

    visit[row][col] = 1 + max(max(up, down), max(l, r));

    return visit[row][col];
}

int longestIncreasingPath(vector<vector<int>> &matrix) {
    maxCol = matrix[0].size();
    maxRow = matrix.size();
    vector<vector<int>> visted(matrix.size(), vector<int>(matrix[0].size(), 0));

    int ret = 0;

    for (int i = 0; i < matrix.size(); ++i) {

        for (int j = 0; j < matrix[0].size(); ++j) {
            ret = max(ret, dfs(matrix, visted, INT_MIN, i, j));
        }

    }


    return ret;

}